package 算法.练习1;

import 算法.NiuKe.TreeNode;

import java.util.Arrays;

/**
 * @author:谢君臣
 * @Date:2021/8/21-22:38
 * @version:1.0
 * @function:
 */
public class 堆排序 {
    public static void main(String[] args) {
        TreeNode root = null;
        int[] arr = new int[]{3,6, 1, 4, 5, 3, 7, 2, 8};
        sort(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int l, int r) {
        while (r > l) {
            for (int i = (r - l) / 2 - 1; i >= 0; i--) {
                int j = i;
                while (2 * j + 1 < r) {
                    int min;
                    if ((j + 1) * 2 < r)
                        min = arr[2 * j + 1] <= arr[2 * j + 2] ? 2 * j + 1 : 2 * j + 2;
                    else
                        min = 2 * j + 1;
                    if (min<r && arr[j] > arr[min])
                        swap(arr, j, min);
                    j = min;
                }
            }
            swap(arr, 0, --r);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
